package algorithm.templates;

import lombok.extern.slf4j.Slf4j;

import java.util.Scanner;

/**
 * @author Seon
 * @date 2023/4/9
 */
@Slf4j
public class DFSTemplate {
    /**
     * ps:测试数据中，1为可行走的，2为障碍物，0为终点
     * 测试数据:
     * 5 4
     * 1 1 2 1
     * 1 1 1 1
     * 1 1 2 1
     * 1 2 1 1
     * 1 1 1 2
     */
    int startX = 1, startY = 1, endX = 4, endY = 3;
    int minStep = Integer.MAX_VALUE;
    int minLinesCnt = 1;
    int[][] data = new int[100][100];
    int[][] view = new int[100][100];
    int[] dX = {0, 1, 0, -1};
    int[] dY = {1, 0, -1, 0};

    public void runDfs() {
        Scanner reader = new Scanner(System.in);
        int m, n;
        // 读入数据
        m = reader.nextInt();
        n = reader.nextInt();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                data[i][j] = reader.nextInt();
            }
        }
        Point point = new Point(startX, startY, 0);
        view[startX][startY] = 1;
        dfs(point);
        System.out.println("minStep is " + minStep);
        System.out.println("minLinesCnt is " + minLinesCnt);
    }

    public void dfs(Point point) {
        if (point.x == endX && point.y == endY) {
            if (point.step < minStep) {
                minStep = point.step;
                minLinesCnt = 1;
            } else if (point.step == minStep) {
                minLinesCnt ++;
            }
            return ;
        }
        // 如果不是终点
        for (int i = 0; i < 4; i ++) {
            int x = point.x;
            int y = point.y;
            // 四个方向依次递归探索, 方向分别为右，下， 左，上。
            int tx, ty;
            tx = x + dX[i];
            ty = y + dY[i];
            if (data[tx][ty] == 1 && view[tx][ty] == 0) {
                view[tx][ty] = 1;
                dfs(new Point(tx, ty, point.step+1));
                view[tx][ty] = 0;
            }
        }
        return ;
    }

    public static void main(String[] args) {
        DFSTemplate dfsApplication = new DFSTemplate();
        dfsApplication.runDfs();
    }
}
